package com.zhugang.week13.dp;

/**
 * @program algorithms
 * @description: Bages2ByDP
 * @author: chanzhugang
 * @create: 2022/09/14 23:47
 */
public class Bages2ByDP {

    /**
     * 二维费用背包
     * dp解决
     *
     * @param weight
     * @param value
     * @param n
     * @param w
     * @return
     */
    public int knapsack(int[] weight, int[] value, int n, int w) {
        // dp[i][j]：第i个物品装入重量为j， 值为最大价值
        int[][] dp = new int[n][w + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                dp[i][j] = Integer.MIN_VALUE;
            }
        }

        dp[0][0] = 0;
        if (weight[0] <= w) {
            dp[0][weight[0]] = value[0];
        }

        /*for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (dp[i - 1][j] == Integer.MIN_VALUE) {
                    continue;
                }
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                if (j + weight[i] <= w) {
                    dp[i][j + weight[i]] = Math.max(dp[i][j + weight[i]], dp[i - 1][j] + value[i]);
                }
            }
        }*/

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
                if (dp[i - 1][j] != Integer.MIN_VALUE) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
                if (j - weight[i] >= 0 && dp[i - 1][j - weight[i]] != Integer.MIN_VALUE) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }

        int res = Integer.MIN_VALUE;
        for (int j = 0; j <= w; j++) {
            res = Math.max(res, dp[n - 1][j]);
        }
        return res;
    }

    public static void main(String[] args) {
        Bages2ByDP bages2ByDP = new Bages2ByDP();
        int[] weight = {2, 2, 4, 6, 3};
        int[] values = {3, 4, 8, 9, 6};

        int result = bages2ByDP.knapsack(weight, values, 5, 9);
        System.out.println(result);

    }
}